package com.zhu.algorithm.sort;

import com.zhu.algorithm.sort.impl.Sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/24/19:54
 * @Description:归并排序
 *
 * 算法步骤
 * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
 *
 * 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
 *
 * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
 *
 * 重复步骤 3 直到某一指针达到序列尾；
 *
 * 将另一序列剩下的所有元素直接复制到合并序列尾。
 */
public class MergeSort implements Sort {

    @Override
    public int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        long A=System.currentTimeMillis();

        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
//        sort(arr,0,arr.length-1,temp);
        mergeSort(arr,temp,0,arr.length-1);

        long B=System.currentTimeMillis();
        System.out.println("归并排序所耗时间： "+(B-A)+"ms");

        return arr;

    }

    /**
     * 归并排序
     * @param arr
     * @param temp
     * @param left
     * @param right
     */
    private void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;

            mergeSort(arr, temp, left, center);
            mergeSort(arr, temp, center + 1, right);

            merge(arr, temp, left, center, right);
        }

    }

    /**
     * 合并
     * @param arr
     * @param temp
     * @param left
     * @param center
     * @param right
     */
    private void merge(int[] arr, int[] temp, int left,int center, int right) {
        int i = left;
        int j = center + 1;
        for (int k = left; k <= right; k++) {
            if (i > center) {
                temp[k] = arr[j++];
            } else if (j > right) {
                temp[k] = arr[i++];
            } else if (arr[i] <= arr[j]) {
                temp[k] = arr[i++];
            } else {
                temp[k] = arr[j++];
            }
        }
        for (int k = left; k <= right; k++) {
            arr[k] = temp[k];
        }
    }


/*
    private void sort(int[] arr,int left,int right,int[] temp){
        if (left < right){
            int middle = (left+right)/2;
            //左半部归并排序，使得左子序列有序
            sort(arr,left,middle,temp);
            //右半部归并排序，使得右子序列有序
            sort(arr,middle+1,right,temp);
            //排列，将两个有序子数组合并操作
            merge(arr,left,middle,right,temp);
        }

    }

    private void merge(int[] arr,int left,int middle,int right,int[] temp){
        int i = left;   //左指针
        int j = middle+1;   //右指针
        int k = 0;  //临时指针
        //归并
        while (i<=middle && j<=right){
            if (arr[i]<arr[j])
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }
        //将左边剩余元素填充进temp中
        while (i<=middle)
            temp[k++] = arr[i++];
        //将右边剩余元素填充进temp中
        while (j<=right)
            temp[k++] = arr[j++];

        //将临时数组元素填入原数组中
        while (left<=right){
            arr[right--] = temp[--k];
        }

    }*/

}
